package com.linyaonan.leetcode.medium._2904;

/**
 * 给你一个二进制字符串 s 和一个正整数 k 。
 *
 * 如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
 *
 * 令 len 等于 最短 美丽子字符串的长度。
 *
 * 返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
 *
 * 对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
 *
 * 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。
 *
 *
 * 示例 1：
 *
 * 输入：s = "100011001", k = 3
 * 输出："11001"
 * 解释：示例中共有 7 个美丽子字符串：
 * 1. 子字符串 "100011001" 。
 * 2. 子字符串 "100011001" 。
 * 3. 子字符串 "100011001" 。
 * 4. 子字符串 "100011001" 。
 * 5. 子字符串 "100011001" 。
 * 6. 子字符串 "100011001" 。
 * 7. 子字符串 "100011001" 。
 * 最短美丽子字符串的长度是 5 。
 * 长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
 * 示例 2：
 *
 * 输入：s = "1011", k = 2
 * 输出："11"
 * 解释：示例中共有 3 个美丽子字符串：
 * 1. 子字符串 "1011" 。
 * 2. 子字符串 "1011" 。
 * 3. 子字符串 "1011" 。
 * 最短美丽子字符串的长度是 2 。
 * 长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。
 * 示例 3：
 *
 * 输入：s = "000", k = 1
 * 输出：""
 * 解释：示例中不存在美丽子字符串。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 100
 * 1 <= k <= s.length
 *
 * @author: Lin
 * @date: 2024/10/31
 */
public class ShortestAndLexicographicallySmallestBeautifulString {

    /**
     * 滑动窗口的思路，遇到1进行count++，当满足等于k统计该子字符串，并且记录长度
     *      如果出现长度一样的则进行比较，只保留最小的那个
     *      如果出现长度小于则直接进行替换
     * @param s
     * @param k
     * @return
     */
    public String shortestBeautifulSubstring(String s, int k) {
        int l = 0;

        // 01011101000111110
        String savedMidStr = s + "1";
        int addCount = 0;

        // l 找到第一个1的位置
        while (l < s.length() && s.charAt(l) != '1') {
            l++;
        }
        int r = l;
        while (l <= r && r < s.length()) {
            if (s.charAt(r) == '1') {
                addCount++;
            }
            if (addCount == k) {
                // 1的个数已经到达k
                String temp = s.substring(l, r + 1);
                // 这块不需要进行替换
                if (temp.length() > savedMidStr.length()) {
                    //
                } else if (temp.length() == savedMidStr.length()) {
                    if (temp.compareTo(savedMidStr) < 0) {
                        savedMidStr = temp;
                    }
                } else {
                    // 直接替换
                    savedMidStr = temp;
                }
                l++;
                while (l < s.length() && s.charAt(l) != '1') {
                    l++;
                }
                addCount--;
            }
            r++;
        }

        return savedMidStr.length() == s.length() + 1 ? "" : savedMidStr;
    }

}
